package first.codeTop.byteDance;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Stack;

/**
 * @ClassName Leetcode199
 * @description:
 * @author: 荣燊
 * @create: 2021-07-27 17:28
 **/
public class Leetcode199 {
    // 二叉树的右视图

    public static void main(String[] args) {

    }

    /**
     * 我们对树进行深度优先搜索，在搜索过程中，我们总是先访问右子树。
     * 那么对于每一层来说，我们在这层见到的第一个结点一定是最右边的结点。
     * 深度遍历，每一层记录这一层最右边的节点
     */
    public static List<Integer> rightSideView(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // key保存层数，value对应这一层的最右节点的值
        HashMap<Integer, Integer> map = new HashMap<>();
        int maxDepth = -1;
        // 保存树中的节点
        Stack<TreeNode> treeNodes = new Stack<>();
        // 保存节点的层数信息
        Stack<Integer> depths = new Stack<>();
        treeNodes.add(root);
        depths.add(0);

        while (!treeNodes.isEmpty()) {
            TreeNode treeNode = treeNodes.pop();
            int depth = depths.pop();
            if (treeNode != null) {
                // 维护最大层数
                maxDepth = Math.max(depth, maxDepth);
                if (!map.containsKey(depth)) {
                    map.put(depth, treeNode.val);
                }
                // 因为是栈，所以是先进后出的
                treeNodes.push(treeNode.left);
                treeNodes.push(treeNode.right);
                depths.push(depth+1);
                depths.push(depth+1);
            }
        }

        // 将map保存的取出
        for (int i=0; i<=maxDepth; i++) {
            result.add(map.get(i));
        }
        return result;
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
